Re: passwd hashing algorithm

David A. Wagner (dawagner@phoenix.Princeton.EDU)
Wed, 19 Apr 1995 00:21:09 -0400 (EDT)

> 
> > 1. 25 iterations of DES with the first 8 bytes of the
> >    password as key, followed by 25 iterations of DES
> >    with the second 8 bytes of password as key.
   [ ... better version deleted ... ]
> > (1) can be broken on a workstation with ~ 2^32 steps (and
> > very little in the way of memory);
> 
> I've never seen anything resembling a convincing argument for this point.
> 

Hrmm, well, I could give you the crypto explanation...do you
want me to?  [Keywords: meet-in-the-middle, birthday attack]

If not, I issue you a challenge.  I've included a small
program at the end which implements (1) using libdes:

$ ./newcrypt abcdefgh 12345678
E7 B3 AF 1E D5 A8 34 10
$ ./newcrypt xxxx yyyy
5D 4F 2F 99 F4  1 69 B3

Compile it with libdes.a and make sure you get the same
output for the test data above (for portability).  Pick
your own two password strings (at most 8 bytes long each)
and send or post the output of the program.

I'll find two password strings of my own which give the
same output (but they're *not* necessarily the same as your
two strings: they just produce the same hash!).

Gimme a week or so to whip up the program and find the
spare CPU cycles -- I'll need 2^36 DES ops, which is just
large enough to be a small pain in the ass for me.

This should be enough to convince you that it's useless
as a password hashing scheme (I hope!).

If I'm mistaken here, I'm sure someone will inform me,
and all the egg will be on my face :-)

> 
> SecureWare uses a mechanism similar to this and it is part of one of
> their security offerings.  I've used a slightly different, but similar,
> approach for several years
> 

Good lord!  Can anyone give more details?  [ The details
tend to matter in this business: something similar but
slightly different might be safe. :-) ]

Sorry to the rest of you bugtraq folks: I would be taking
this to personal email, except for the fact that someone
actually uses the broken scheme -- yikes! -- that's my ObBug.

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu



/* newcrypt.c -- Dave Wagner dawagner@princeton.edu */
#include <stdio.h>
#include "des.h"

#define ITERS	25

do_onekey(in, k)
	des_cblock	*in;
	unsigned char	*k;
{
	des_cblock	out, key;
	des_key_schedule	sched;
	int	i;

	bzero((unsigned char *) &key, sizeof(des_cblock));
	strncpy((unsigned char *) &key, k, sizeof(des_cblock));
	des_set_odd_parity(&key);
	des_set_key(&key, sched);

	for (i=0; i<ITERS; i++) {
		des_ecb_encrypt(in, &out, sched, /* encrypt */ 1);
		bcopy(&out, in, sizeof(des_cblock)); /* in := out; */
	}
}

main(argc, argv)
	int	argc;
	char	**argv;
{
	des_cblock	in;
	unsigned char	*p;
	int	i;

	if (argc != 3) {
		fprintf(stderr, "Usage: %s key1 key2\n", argv[0]);
		exit(1);
	}
	bzero(&in, sizeof(des_cblock));
	do_onekey(&in, argv[1]);
	do_onekey(&in, argv[2]);

	p = (unsigned char *) &in;
	for (i=0; i<8; i++)
		printf("%2X ", *p++);
	printf("\n");

	return(0);
}